One important task in implementing a circuit design is placement. Placement refers to the process of assigning coordinate locations from an abstract grid representation of a particular target device, such as a programmable logic device (PLD), to various blocks and pins of the circuit design. The objective of placement is to assign circuit blocks to locations of the target device such that signals linking the blocks and pins can be routed to meet established design requirements relating to the number of routing resources used, power consumption, timing requirements, etc. Typically, this is one by minimizing a cost function involving these and/or other design parameters. Estimated wire length, for example, is one type of cost function which serves as a simple first order approximation for circuit attributes such as timing, area, and congestion.
Recursive partitioning, also referred to as “min-cut partitioning”, is an example of a top-down placement technique. Recursive partitioning calls for dividing the circuit design and target device into a plurality of smaller partitions. Graph-based partitioning techniques can be used to subdivide the circuit design. The circuit design is recursively partitioned, or subdivided, into smaller and smaller portions until the resulting partitions fit into a unit area of the target device.
One way of partitioning a circuit design is to use a cost function that depends upon design cutset when creating design-cutlines. A design-cutline refers to the line or boundary that creates two or more partitions from a single larger partition of the circuit design. The design-cutset for a particular design-partitioning step refers to the number of wires of the circuit design that crosses the design-cutline. Typically, the cost function seeks to minimize the design-cutset when determining the design-cutline, while also attempting to maintain a balance between the area of each resulting circuit design partition. Minimizing the design-cutset, in general, correlates to the minimization of total wire length in the circuit design.
A target device, such as a field programmable gate array (FPGA), can be modeled such that a uniform distribution of pre-fabricated wires is assumed to exist throughout the device. As such, the number of wires running across a given unit area of the target device can be assumed to be constant. Conventional approaches to partitioning-based placement have focused on creating device-partitions using rectilinear device-cutlines. A device-cutline refers to the line or boundary that creates two or more device-partitions from a single larger device-partition of the target device. Portions of the target device are subdivided using straight device-cutlines, resulting in rectangular device-partitions. Thus, it can be assumed that a straight device-cutline cuts across a number of wires that is proportional to the length of the device-cutline.
A straight device-cutline generally provides minimal wire-bandwidth. Wire bandwidth refers to the number of wires of the target device that cross a given device-cutline, whether such wires are used by the circuit design or not. A higher wire-bandwidth generally is indicative of increased site availability adjacent to the device-cutline for component placement within device-partitions created by the subject device-cutline. A lower wire-bandwidth generally is indicative of limited site availability adjacent to the device-cutline for placement within the device-partitions created by the subject device-cutline.
When sites adjacent to the device-cutline are not available, components have to be placed in the interior of the device-partitions. This leads to increased lengths of wires connecting components across the subject device-cutline. Accordingly, higher wire-bandwidth implies that more connected components can be placed such that the lengths of the wires that are cut the by the device-cutline are minimized. With this in mind, the use of rectilinear device-cutlines can lead to reduced quality of results for placement solutions as the number of sites available for component placement within partitions is reduced or minimized.
It would be beneficial to provide a technique for recursive partitioning that addresses the limitations described above.